
%--------------------------
%      计算复杂性理论
%--------------------------

%\chapter{计算复杂性理论}
\section{简介}
这里我们引用Arora在其Computational Complexity: A Modern Approach(计算复杂性:现代方法)一书\cite{Arora计算复杂性}中的序言部分内容作为本节内容\footnote{此书的网页在\url{https://theory.cs.princeton.edu/complexity/}}。\par

\vspace{0.5cm}
如果一个科学分支还能找到大量的研究问题，则这个分支还活着；研究问题的缺失则预示着这个科学分支的消亡或者独立发展的终结。——戴维·希尔伯特(David Hilbert),1900\par
\vspace{0.5cm}
我演讲的主题或许可以直接用两个简单的问题来揭示。第一个问题是，乘法比加法更难吗？而第二个问题则是，为什么？……我(想)要证明不存在乘法的算法在计算上同加法的算法一样简单，这就证明了乘法计算中确实存在某种绊脚石。——阿兰·科巴姆(Alan Cobham),1964\par
\vspace{0.5cm}

几千年来，人们在账目管理和天文学中不断地进行着各种计算，因此计算的概念以这种形式一直存在着。例如，利用计算可以求解下面的任务。\par
\begin{itemize}
	\item 给定两个整数，计算它们的乘积。
	\item 给定n个变量上n个方程构成的方程组，找出它的一个解（如果解存在的话）。
	\item 给定一个熟人列表和这些人中彼此不能和睦相处的一些人员对，找出你在宴会中打算邀请的最大熟人子集使得他们彼此都能够和睦相处。
\end{itemize}


在历史长河中，人们总结得出：在概念上，计算就是在给定的输入上用有限个步骤得到输出的过程。他们认为，“计算”就是“在演草纸上根据一定规则写出一些数字的人”。\par

20世纪中叶，科学上的一项重要突破就是对“计算”的精确定义。根据这个定义，人们马上清楚了计算其实就存在于各种物理系统和数学系统中——图灵机(Turing machine)，λ演算（Lambda calculus），细胞自动机(cellular automata)，指针机(pointer machine),弹跳桌球(bouncing billiards ball)，康韦生命游戏(Conway’s game of life)，等等。出人意料的是，这些形式的计算都是等价的，也就是说，其中一个模型能够实现的所有计算也能在其他模型上完成。在这种认识的基础上，人们马上发明了能够执行所有程序的硬件，这就是标准的通用电子计算机。在接下来的几十年中，计算机迅速被社会接纳，这使得计算融入了现代生活的方方面面，也使得计算问题在设计、计划、工程、科学发现等人类活动中变得越来越重要，于是计算机算法（亦即，求解计算问题的各种方法）变得无处不在。\par

然而，计算并不“仅仅”是一种用于实践的工具，它也是一个主要的科学概念。事实上，科学家现在将许多自然现象都视为一种计算过程，这些计算过程实际上是细胞自动机的推广。例如，对生物繁衍过程的理解曾经导致了自体复制计算机的发现。再比如，物理学家薛定谔(Schroedinger)曾在他的书中预言细胞中肯定存在类似于DNA的物质，后来沃森(Watson)和克里克(Crick)发现了这种物质，克里克坦承他们的研究正是受到了薛定谔的工作的启发。如今，各种计算模型已经成为生物学和神经科学中许多领域研究的基础。电子电动力学(QED)等几种物理理论的本征刻画非常类似于计算的定义，这种现象甚至还促使一些科学家相信整个宇宙就是一台超级计算机。更有趣的是，这样的物理理论在过去的十年中已经被用于设计量子计算机。\par
\textbf{可计算性与计算复杂性}
\par
研究者在成功地给出计算的概念之后,开始研究什么样的问题是可计算的。他们证明了几个有趣的问题本质上都不是可计算的，也就是说，没有计算机能够求解这些问题而不在任何输入上陷入无限循环（即不停机）。可计算性理论是一个很重要的专题。计算复杂性理论，它关注计算的效率，也就是量化地研究求解给定计算任务所需的计算资源的数量。
\par
\textbf{计算效率的量化}
\par
我们用前面提到的三个计算任务来阐释计算效率的含义。首先，考虑两个整数的乘法。我们可以用两种不同的方法（或算法）来完成这项任务。第一种方法是累加算法；也就是说，为了计算a·b，只需用b-1次加法将b个a进行累加。第二种方法是小学列式算法。虽然累加算法比小学列式算法简单，但我们总觉得后者比前者更好。事实上，小学列式算法的效率更高。例如，计算577乘以423时，累加算法需要计算422次加法；但小学列式算法却只需将其中一个数分别与3个一位数相乘，再计算3次加法。\par

算法效率的量化就是研究算法所执行的基本操作个数随着输入规模的增长是如何变化的。在整数乘法中，单个数位相加或相乘就是基本操作（在其他场合中，除法也可以是基本操作），而两个因数中的数位个数就是输入规模。在计算两个n位整数的乘法时（也就是说，两个因数都大于$10^n-1$且小于$10^n$）,小学列式算法执行的基本操作数不超过$2n^2$，而累加算法执行的基本操作数至少是$n10^n-1$。经过这样的分析，两种算法之间的巨大差异就显而易见了。即使计算两个11位整数的乘法，执行小学列式算法的便携式计算器也会快于执行累加算法的超级计算机。对于稍大一些的整数，小学五年级学生用笔和纸执行列式算法也会胜于执行累加算法的超级计算机。由此可见，算法的效率明显比运行算法所用的技术要重要得多。\par

更令人意外的是，借助傅里叶变换可以设计出更快的乘法算法。这个算法40年前才被人们发现，在这个算法中，两个n位整数的乘法仅用$cn\log{n} \times loglog{n}$个操作就可以完成，其中c是独立于n的绝对常数。随着n的增大，该算法执行的基本操作数将远小于$n^2$。\par

对于线性方程组的求解，经典的高斯消元法用$O(n^3)$个基本的算术操作就可以求解n个变量上n个方程构成的方程组（虽然这一算法用高斯的名字命名，但早在公元1世纪中国数学家就已经掌握了这种算法的某种形式）。20世纪60年代末，斯特拉森(Strassen)找到了更加高效的算法，该算法大约只需要执行$O(n^{2.81})$个操作就能求解这个问题。目前，求解这一问题的最佳算法需要执行$O(n^{2.376})$个操作。\par

　　宴会问题也有一段有趣的历史。同乘法的情况一样，宴会问题也存在显而易见的简单低效算法——从大到小地依次枚举n个人的每个子集，直到找到一个子集使得其中不含任何两个无法和睦相处的人。这个算法需要执行的计算步骤数可能与n个人的所有子集数一样多，亦即$2^n$。这使得该算法根本无法用于实践，因为如果某人用这个算法来安排一个70人参加的宴会，即使她用超级计算机来进行处理，也需要提前一千年开始筹备。但出乎意料的是，人们至今仍没有为宴会问题找到效率显著更优的算法。事实上，我们有理由怀疑宴会问题不存在高效的算法，因为我们可以证明它等价于独立集这个计算问题，而独立集问题以及其他成千上万个计算问题都是NPC完全问题。著名的$P\stackrel{?}{=}NP$问题是问：有没有哪个NPC完全问题存在高效的算法?
　　\par

\textbf{证明高效算法的不存在性}\par

我们已经看到，某些计算任务存在非平凡的算法使得其效率比几千年来人们一直使用的算法更高。一件特别有意义的事情是：证明某些组合任务的当前算法是最佳的。也就是说，这些计算任务不存在更有效的算法。例如，我们可以证明整数乘法的$O(nlognloglogn)$步算法无法进一步改进，这就说明乘法在本质上确实比加法更难，因为加法存在$O(n)$步算法。再比如，我们还可以证明，没有算法能用少于$2^{n/10}$个计算步骤来求解宴会问题。证明这样的结论是计算复杂性的一个核心任务。\par

如何才能证明这种不存在性呢？求解计算任务的算法可能有无穷个！因此，我们只能用数学手段证明其中的每个算法都比已知的算法更低效。这种方法之所以可行，是因为计算本身也是一个精确的数学概念。事实上，一旦这样一个结果被证明，则它必然吻合于数学上的某个不可能性结果，例如，几何中其他公理无法推导出欧几里得平行公理、尺规作图无法三等分一个角等。这些结论都是数学上最有价值、最可靠和最出人意料的结果。\par

在复杂性理论中，我们很少能证明这种不存在性结果。但是，在能力弱于一般计算机的计算模型上，我们确实已经证得了一些重要的不存在性结果。由于在一般的计算机上我们还缺少这样的好结果，因此复杂性理论在一般计算机上获得的重要结果指的是在不同复杂性问题之间建立的相互联系。人们在这方面获得了很多漂亮的结果。\par

\textbf{关于计算效率的几个有趣问题}\par

现在，我们概述关于计算复杂性的几个重要问题。\par
1.生命科学、社会科学和运筹学等学科中的很多计算任务都通过搜索海量的解空间来找出问题的解。比如，前面已经提到的线性方程组的求解和宴会问题中找出最大的受邀者集合都属于这种情况。这种搜索通常称为穷举搜索，因为搜索过程穷举了所有的可能。这种穷举搜索能替换为更有效的算法吗？\par

2.用随机性（即硬币投掷）能加快算法的计算速度吗？\par

3.如果允许算法在小部分输入上出错，或者只要求算法求得问题的近似解，那么难解的问题会变得容易一些吗？\par

4.计算上的难解问题对实践有什么帮助呢？例如，我们能借助这些难解问题构造出牢不可破的密码协议吗（至少相对于大家认可的敌手而言）？\par

5.我们能利用物质的违背直觉的量子力学性质建造出更快的计算机吗？\par

6.只有人才能证明数学定理吗？换句话说，数学证明能被自动生成吗？能在不完整阅读数学证明的情况下验证数学证明的真伪吗？证明者和验证者通过对话来完成的交互式证明比标准的“静态”数学证明更有效力吗？\par

证明是数学上的核心概念。事实证明，它也是计算复杂性的核心概念。而且，计算复杂性已经对数学证明的含义赋予了新的解释。数学证明能否自动生成将取决于$P\stackrel{?}{=}NP$问题的答案。概率可验证明(Probabilistic Checkable Proof)是一种健壮的数学证明，要查验这种证明的真伪，只需概率地选取证明中的少数几个位置进行查验即可。相比之下，传统的证明则需要逐行阅读才能查验其真伪。类似地，用交互式证明的概念得出了一些出人意料的结果。还有研究证明复杂性的，它是复杂性的一个子领域，研究各种命题的最小证明长度。\par

历经近40年\footnote{本书出版在2016年左右}的发展，复杂性理论仍是一门年轻的科学，许多重要结果的发现还不到20年。上述这些问题还没有被完全解决。一个令人意外的转折是，复杂性理论被用于某些数学定理的证明中：它们提供的证据表明计算复杂性中某些问题是难解的。\par


\section{什么是计算?}
\textit{所谓计算，是指通过重复使用一种预先制定的规则来改变环境的过程。这里有一个关键性限制条件是规则必须是简单的：在每次应用时，只依赖于且只影响环境的一(小)部分。虽然每次使用规则时只产生极其有限的影响，但多次使用之后，结果将异常复杂。换言之，计算会把与之相关的环境变得非常复杂，但其过程只是重复简单的规则。}
\par
\textit{可以用计算这一概念对自然现象的“机械化”部分建立模型，就是说，确定现实(而非现象在某个特定时刻的特殊状态)演变的规则。此时，研究的出发点是自然现象的实际演化过程，而研究的目的是找到这个自然过程背后的规则。在某种意义上，科学研究的目标总体上可以描述为寻找支配各种自然现象(或者这些现象的抽象)的规则。}
\par
\textit{计算机算法是由人类设计的计算规则，借此可以对相应的人造环境产生特定的期望效果。}\par
\textit{为了严格地定义计算，需要指定计算模型，即对于计算环境及可应用于该环境中的一类规则提供具体定义。这种模型对应着实际计算中计算机的抽象。常使用的一个简单抽象模型是图灵机(Turing Machine)，因此算法通常由相应的图灵机来形式化定义。然后，需要强调的是，计算理论中的许多结论，并不考虑特定的计算模型，只要模型是“合理”的即可。}
\cite{Goldreich计算复杂性}\footnote{此书的网站上有电子版可以下载，网址\url{https://www.wisdom.weizmann.ac.il/~oded/cc-drafts.html}}
\par
\vspace{0.5cm}

计算其实是一个过程，算法是一个实例化的计算过程，一个算法或者一个计算过程最后其实是确定了一个函数。要严格定义计算，需要设计一个计算模型，图灵在1936年其发表的论文中，第一次创造性地提出了一个抽象的一般化的计算模型，为计算研究或者说自动计算打开了一扇大门。

\section{计算的数学定义(形式化描述)}
自从图灵给出人类第一个计算模型图灵机后，陆续又提出几个不同的计算模型，这些计算模型在讨论模型问题时都有其优势，同时这些图灵机均被证明与图灵机计算能力等价，也就是一个模型能计算的，另外一个模型也能计算，一个模型不能计算，另外一个模型也不能计算。

\subsection{确定型图灵机(Deterministic Turing Machine)}
\subsubsection{描述性定义}
1936年，英国数学家阿兰・麦席森・图灵(1912―-1954年)提出了一种抽象的计算模型——图灵机( Turing machine)。图灵机，又称图灵计算机，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。\par

所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。\par

图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作： \par
1、在纸上写上或擦除某个符号； \par 
2、把注意力从纸的一个位置移动到另一个位置。 \par
而在每个阶段，人要决定下一步的动作，依赖于 (1) 此人当前所关注的纸上某个位置的符号和(2) 此人当前思维的状态。\par 
为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成： \par
1、一条无限长的纸带 TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0，1，2，... ，纸带的右端可以无限伸展。 \par 
2、一个读写头 HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。 \par 
3、一套控制规则 TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。 \par 
4、一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。参见停机问题。\par 
注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。\par

\subsubsection{形式化定义}
我们这里描述的是一个最简单的图灵机，确定型图灵机(Deterministic Turing Machine)，通常缩写为DTM，下面我们对图灵机进行形式化描述,即使是图灵机的形式化定义，不同资料上给出的也略有不同，但是都是等价定义。\par

一台图灵机是一个七元组，$\{Q,\Sigma,\Gamma,\delta,q_0,B,F\}$，其中 $\Sigma,\Gamma,\delta$ 都是有限集合，且满足： \par
1、$Q$ 是状态集合； \par 
2、$\Sigma$ 是输入字母表或者是输入符号的有穷集合，其中不包含特殊的空白符B； \par 
3、$\Gamma$ 是带字母表，也有称为带上可用字符集合，其中 $\Sigma \subset \delta$ ；\par
4、$\delta:Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\} $ 是转移函数，其中L，R 表示读写头是向左移还是向右移；\par
5、$q_0\in Q是$起始状态，$q_0\in Q$；\par
6、B空白符号\footnote{有的参考资料上写的是空格符号，但是这个叫法有时候会和我们键盘上的空格在理解上混淆，但其实两个含义完全不一样，因为键盘上空格依然是一个符号，但是图灵机里这个空格符号没有任何实际意见，所以此处我们称为空白符号。}，$B\in \Gamma,B \notin \Sigma $,开始时B出现在除包含输入符号的有穷多个初始单元之外的所有单元中。\par
7、F是终结状态或拒绝状态$q_{reject}$和接受状态$q_{accept}$的集合，且$q_{reject}\neq q_{accept}$，$F \subset Q$。 \par

图灵机 $\{Q,\Sigma,\Gamma,\delta,q_0,B,F\}$ 将以如下方式运作：\par 
开始的时候将输入符号串从左到右依此填在纸带上， 其他格子保持空白（即填以空白符）。M 的读写头指向第 0 号格子， M 处于状态 $q_0$。机器开始运行后，按照转移函数 $\delta$所描述的规则进行计算。例如，若当前机器的状态为 $q$，读写头所指的格子中的符号为 $x$，设 $\delta(q,x)=(q',x',L)$， 则机器进入新状态 $q'$， 将读写头所指的格子中的符号改为 $x'$， 然后将读写头向左(L)移动一个格子。若在某一时刻，读写头所指的是第 0 号格子， 但根据转移函数它下一步将继续向左移，这时它停在原地不动。换句话说，读写头始终不移出纸带的左边界。若在某个时刻 M, 根据转移函数进入了状态 $q_{accept}$， 则它立刻停机,并接受输入的字符串； 若在某个时刻 M 根据转移函数进入了状态 $q_{reject}$， 则它立刻停机并拒绝输入的字符串。 \par 

注意，转移函数  $\delta$ 是一个部分函数， 换句话说对于某些 $q,x, \delta(q,x)$可能没有定义， 如果在运行中遇到下一个操作没有定义的情况， 机器将立刻停机。 \par

为了形式化地描述图灵机的运转过程，引入格局(configuration)或瞬时描述(instantaneous description),格局对当前图灵机的状态进行了完整描述，格局是一个三元组$(q,w,u)$,q是当前状态，w是读写头左边字符串，u是读写头右边字符串，读写头正扫描u的最左面的符号，我们也通常记为$wqu$，而用$\vdash$表示格局变化。
\par
\vspace{1cm}

\begin{example}\cite{堵丁柱2002计算复杂性导论}
	我们来描述一个接受语言$L=\{a^i b a^j | 0\leq i \leq j \}$ 的图灵机 M，M有状态集合$Q=\{q_0,q_1,q_2,q_3,q_4,q_5\}$，初始状态$q_0$,接受状态集合为$\{q_5\}$,输入符号集合$\Sigma = \{a,b\}$,带用符合集合$\Gamma =\{a,c,c,B\}$,B为空格符号，图灵机的转移函数$\delta$如下表定义：\\
	\begin{table}[h]
		\centering
		
		\begin{tabular}{|c|c|c|c|c|}
			\hline 
			$\delta$ & a & b & c & B \\ 
			\hline 
			$q_0$ & $q_1,c,R$ & $q_4,B,R$ & $q_0,B,R$ &  \\ 
			\hline 
			$q_1$ & $q_1,a,R$ & $q_2,b,R$ &  &  \\ 
			\hline 
			$q_2$ & $q_3,c,L$ &  & $q_2,c,R$ & $q_2,B,R$ \\ 
			\hline 
			$q_3$ & $q_3,a,L$ & $q_3,b,L$ & $q_3,c,L$ & $q_0,B,R$ \\ 
			\hline 
			$q_4$ & $q_4,a,R$ &  & $q_4,B,R$ & $q_5,B,R$ \\ 
			\hline 
		\end{tabular}
	\end{table}
	在描述状态转移函数的状态转移表中，第一个参数表示转移的状态，第二个参数表示在当前位置写入的符号，第三个表示移动方向，比如第二行第二列的$q_1,c,R$，表示当前状态为$q_0$,读头下是a(也就是说读取a)是，转移到状态$q_1$,并且写入c(也就是把原来的a改写为c)，然后向右移动。\par
	容易看出，对所有L中符号行，M都能停在状态$q_5$中，对于符号行$a^i b a^j (i \geq j \geq 0) $,M无法停机，对于不含符号b或者含两个以上b的符号行w，M也能停机，但是停在非接受状态中，下面是三种运算过程的例子：\par
	
	(1)在输入abaa时(停机，接受)：$q_0abaa \vdash  cq_1baa \vdash cbq_2aa \vdash cq_3bca \vdash q_3cbca \vdash q_3Bcbca \vdash q_0cbca \vdash q_0bca \vdash q_4ca \vdash q_4a \vdash aq_4B \vdash aBq_5B$ 。\par
	
	(2)在输入aaba时(不停机)：$q_0aaba \vdash cq_1aba \vdash caq_1ba \vdash cabq_2a \vdash caq_3bc \vdash cq_3abc \vdash q_3cabc \vdash q_3Bcabc \vdash q_0cabc \vdash cq_1bc \vdash cbq_2c \vdash cbcq_2B \vdash cbcBq_2B \vdash cbcBBq_2B \vdash \ldots$。\par
	
	(3)在输入abab时(停机，但不可接受)：$q_0abab \vdash cq_1bab \vdash cbq_2ab \vdash cq_3bcb \vdash q_3cbcb \vdash q_3Bcbab \vdash q_0cbcb \vdash q_0bcb \vdash q_4cb \vdash q_4b$。\par
\end{example}
\vspace{1cm}

\begin{definition}{}{int}\cite{堵丁柱2002计算复杂性导论}
	(a)如果对$\Sigma$上的语言A，存在图灵机M，A是M可接受语言，那么称A为图灵机可接受集，或递归可枚举集，简称为r.e.集。\par
	(b)如果对$\Sigma$上的语言A和它的补集$\overline{A} = \Sigma ^* -A$都是图灵可接受集，那么称其为图灵可判定集，或者说它是递归集。\par
	(c)如果对部分函数$f:\Sigma ^* \rightarrow \Sigma ^*$,如果存在图灵机M使得(i)将f的定义域中w输入M时所得输出为$f(w)$，(ii)将f的定义域外之w输入时，M无法停机，那么称f为可计算函数，或者说部分递归函数。\par
	(d)如果一个部分递归函数f的定义域等于$\Sigma ^*$，则称f为全递归函数，或递归函数。
	
\end{definition}	

\vspace{1cm}

在大多数研究者阐明图灵机的时候都会结合语言来讲计算模型，但是也有部分学者不建议在介绍图灵机概念时引入语言，其认为这对于理解图灵机的实质并无益处。
\par

\vspace{1cm}

\begin{example}
	设计一个二进制的非操作图灵机。
\end{example}
\begin{solution}
	输入字符集$\Sigma=\{ 0,1 \}$，带字母表$\Gamma=\{0,1,N\}$，其中N是空白符(null)，这是一个3-symbol图灵机，此图灵机执行过程为：从一个小方格子里读出symbol；清除一个小方格子里的内容，或者直接写入新的symbol覆盖原有的数据；向左（右）移动。总共有三种状态$\{state_0,state_1,stop \}$状态转移函数为：
	\begin{table}[h]
		\centering
		\begin{tabular}{|c|c|c|c|}
			\hline 
			$\delta$ & 0 & 1 & N \\ 
			\hline 
			$state_0$ & $state_1 ,1,R$ & $state_1 ,0,R$ & $state_1 ,N,R$ \\ 
			\hline 
			$state_1$ & $state_1 ,1,R$ & $state_1 ,0,R$ & $stop ,N,R$ \\ 
			\hline 
			$stop$ &  &  &  \\ 
			\hline 
		\end{tabular} 
	\end{table}
	
	如果输入010，其计算过程为(为了表达方便，用$s_i$表示状态$state_i$)：\\
	$s_0 010 \vdash 1 s_1 10 \vdash 10 s_1 0 \vdash 101 s_1  \vdash stop$
	\par
	注意，因为传输带是无限长，所以$101 s_1 = 101 s_1 N$。
\end{solution}
\vspace{1cm}

\begin{example}
	设计一个二进制加法图灵机。
\end{example}
\begin{solution}
	在这里我们把一个二进制数直接表示为0的个数，比如101(十进制的5)，我们表示为"00000"，加法用“c”来表示，比如00c000，就是表示2+3，对于这个计算带的输入就是“00c000”,我们可以看到对于这样的编码，加法图灵机的状态转移函数变的很简单$(q_0,0)\rightarrow (q_1,0,R),(q_0,c)\rightarrow (q_{reject},c,R),(q_1,0)\rightarrow (q_1,0,R),(q_1,c)\rightarrow (q_1,0,R),(q_1,B)\rightarrow (q_{accept},B,R)$.\par
	用自然语言来描述就是把c换成0即可。
\end{solution}

\subsection{随机存取机(Random-Access Machine,RAM)}

随机存取机(Random-Access Machine,RAM)是冯$\cdot$诺依曼在其1945年的一个技术报告\footnote{First Draft of a Report on the EDVAC}中提出的一个计算模型，下面我们简单描述以下这个模型\cite{Goldreich计算复杂性}。一个抽象的RAM包含任意多个存储单元，数量有限的寄存器，其中一个程序计数器，以及由有限个指令构成的程序，可能的指令集合包含以下指令：
\begin{itemize}
	\item $reset(r)$:r为寄存器编号，此指令将寄存器r的值置0。
	\item $inc(r)$:r为寄存器编号，此指令为增加r的值。类似dec(r),使寄存器r的值减小。
	\item $load(r_1,r_2)$:$r_1,r_2$为寄存器编号,此指令将存储位置m处的值存入寄存器$r_1$中，而m为寄存器$r_2$中存储的内容。
	\item $store(r_1,r_2)$:将寄存器$r_1$中的值存储到内容中，此内容位置记录在$r_2$中。
	\item $cond-goto(r,l)$：r为寄存器序号，l为不大于程序长度的整数，此指令表示，如果寄存器r中保存的值非负，则程序计数器的值置为l-1.
\end{itemize}
每条指令执行后，程序计数器的值加1，程序计数器的指针移到下一条要执行的指令(当程序计数器的值超过程序长度时停机)，可以将前n个存储单元的内容定义为机器的输入，其中n的值保存于一个特殊的寄存器中。\par

可以证明这个抽象的RAM可以由一个图灵机来模仿，也就是说RAM的计算能力不超过图灵机。反之如果我们可以证明用RAM来模拟图灵机，那么就是说明两种模型计算能力等价。


\subsection{布尔电路(Boolean Circuits)}

布尔电路计算模型比图灵机模型更加简单，在证明复杂性下界时比图灵机证明更加容易一些。\par

\begin{definition}{布尔线路}{int}\cite{Arora计算复杂性}
	对任意$n\in N $,一个n输入单输出的布尔线路是具有n个源顶点和1个汇顶点的有向图。源顶点也称输入顶点，指的是入度为0的顶点。汇顶点也称输出顶点，指的是出度为0的顶点，每个非源顶点称为一个逻辑门，并用逻辑操作$\wedge$(与)、$\vee$(或)、$\neg$(非)中的一个操作进行标记。顶点的扇入度指的是进入该顶点的边的条数。标价为和的顶点的扇入度等于2，而标记为的顶点的扇入度等于1。如果C是一个布尔线路，而$x\in \{0,1\}^n$是他的一个输入，则将C在x上输出记为$C(x)$，定义每个顶点v的输出值为$val(v)$，如果v是第i个源顶点，则$val(v)=x_i$。$C(x)$是C的输出顶点的值。	
\end{definition}	
\par

在有些书籍里布尔电路定义是n输入m输出，这个没有大的影响，因为我们可以证明，可以用n输入1输出的布尔电路来模拟n输入m输出。\par

研究布尔线路的动机之一是为了给硅芯片设计一个数学模型，但是后来作为研究计算复杂性的计算模型了。\par

布尔电路的规模是指其边的个数，对于计算函数$f:(0,1)^* \rightarrow \{0,1\}$的电路簇$(C_n)_{n\in N}$，可以将$C_n$的规模看做是关于n的函数，$s(n),s:N\rightarrow N$,函数f的电路复杂度记为$s_f$，是所有可计算f的电路簇的规模复杂度下确界。\par

电路复杂度具有如下一些定理\cite{Goldreich计算复杂性}：
\begin{enumerate}
	\item 任意一个布尔函数都可由某类电路计算，并且电路复杂度最多为指数级。也就是说函数$f:\{0,1\}^* \rightarrow \{0,1\}$可由规模为$O(n2^n)$的电路计算，这个电路实现的是查表运算。
	\item 一些函数具有多项式的电路复杂度，特别是任意一个时间复杂度为t的函数(即可由时间复杂度为t的算法计算的函数)具有poly(t)的电路复杂度，也就是说具有多项式的电路复杂度。(证明思路：考虑计算该函数的图灵机，及其对于n比特输入的计算，相关计算过程可以用一个t(n)层电路模仿，电路的每一层代表机器的一种中间格局。)
	\item 几乎所有的布尔函数都有指数级的电路复杂度，特别地，可由规模为s的电路计算的$\{0,1\}^n \rightarrow \{0,1\}$的映射个数小于$s^{2s}$。
\end{enumerate}
\par
多项式规模的电路簇被称为一致的，如果一个函数可以由一致的多项式规模电路簇计算，则他也可以由多项式时间算法计算。
\par

\subsection{判定树(Decision tree)}

目前图灵计算能力相关的一些基本问题仍然远未解决，于是，为了用其他方式深刻地理解"高效计算"这一难以琢磨的概念，人民转而研究更简单的限制性更强的计算模型，在这些模型中最简单的就是判定树。\cite{Arora计算复杂性}\par

\begin{definition}{判定树}{int}\cite{Arora计算复杂性}
	设$f:\{0,1\}^n \rightarrow \{0,1\}$是一个函数，构造计算f的判定树如下，每个内部节点标记为形如$x_i$，并且其恰有两条分别被标记为0和1的出边，每个叶节点被标记为输出0或1。在输入$x=x_1 x_2 \ldots x_n$时，计算过程为，更加节点自身的标记来检查输入中相应的二进制位$x_i$，如果$x_i=1$，则计算从该顶点出发，沿1边移动到下一节点，如果$x_i=0$，则计算从该顶点出发，沿0边移动到下一节点，一直到页节点，输出结果。	
\end{definition}

\begin{example}
	构造一个判定树，计算3位的多数函数(majority function)。多数函数是这样的函数，如果3个二进制中至少有两个1，结果为1，否则结果为0。
\end{example}
\begin{solution}
	3位多数函数的判定树如图\ref{fig:3bit-majority-fun}所示.
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=0.6\textwidth]{figure/3bit-majority-fun.png}
		\caption{3位多数函数的判定树\label{fig:3bit-majority-fun}}
	\end{figure}
\end{solution}

\subsection{$\lambda$演算($\lambda$ Calculus)}
$\lambda$演算(Lambda Calculus 或 $\lambda$ Calculus)是阿隆佐·邱奇(Alonzo Church)在20世纪30年代其指导学生陆续提出的概念\footnote{关于Church的详细的生平可以看Manzano, Maía 于1997发表的论文， Alonzo church:his life, his work and some of his miracles. History and Philosophy of Logic, 18(4), 211–232. doi:10.1080/01445349708837290 }，在1941年对这部分工作进行总结出版了一书“The Calculi of Lambda-Conversion”。\par

邱奇和图灵是生活在一个年代的人，其提出的$\lambda$演算与图灵机一样，都是想探寻计算的本质，讨论机械/自动计算。关于演算的基本介绍可以参考英文介绍“The Lambda Calculus for Absolute Dummies (like myself)”\footnote{The Lambda Calculus for Absolute Dummies (like myself),网络链接：\url{http://bach.ai/lambda-calculus-for-absolute-dummies/}},Brilliant网站关于Lambda Calculus的介绍\footnote{Lambda Calculus,\url{https://brilliant.org/wiki/lambda-calculus/}}，以及一个外文介绍的中文翻译“Good Math/Bad Math的Lambda演算系列的中文翻译”\footnote{Good Math/Bad Math的Lambda演算系列的中文翻译,网络链接：\url{http://cgnail.github.io/academic/lambda-index/}}。
\par

$\lambda$演算表达式由3个元素组成，变量，函数和应用，演算过程就是将表达式进行简单的查找替换，而这样的模型计算能力与图灵机等价。\par


我们可以将$\lambda$表达式用以下BNF范式(Backus-Naur form)表达的上下文无关文法描述：
\begin{enumerate}
	\item <expression> := <name> | <function> | <application>
	\item <function> := $\lambda$ <name>.<expression>
	\item <application> := <expression><expression>
\end{enumerate}
其中name也称为变量(variable)，可以是任何字母a,b,c等等。
\par
\begin{example}
	函数$f(x)=x$的$\lambda$表达式为：$\lambda x \cdot x$
\end{example}

\begin{example}
	当对表达式$(\lambda x \cdot x) a$求值时，就是把函数体中所有出现的$x$都替换为$a$,如$(\lambda x.x)a $求值结果为$a$。虽然lambda演算传统上只支持单参数函数，但我们可以用一种被称为柯里化（currying）的技巧来创造多参数函数，如$(\lambda x.\lambda y.\lambda z.xyz)$表达的函数是$f(x,y,z)=((xy)z)$ 。
\end{example}

必须意识到经典的$\lambda$演算没有数，字符，或任何非函数的数据类型。\par

\begin{example}
	在$\lambda$演算中没有True或False，也没有1或0。布尔逻辑的表达方式为：
	T表示为$\lambda x.\lambda y.x$,F表示为$\lambda x.\lambda y.y$。
	然后我们定义一个IF函数$\lambda btf$，如果$b$ 为True返回$t$ ，如果$b$为False返回$f$,IF等价于$\lambda b.\lambda t. \lambda f.btf$，使用IF函数，我们可以定义基本的布尔逻辑运算符：
	$a AND b$等价于$\lambda ab.IF a b F$；$a OR b$等价于$\lambda ab.IF a T b$;$NOT a$等价于$\lambda a.IF a F T$。此处$IF a b c$也可写为$IF((a b) c )$。
\end{example}

\begin{example}
	虽然Lambda演算没有数字，但我们可以用Church数来对数字编码。	
	对于任意数n：$n=\lambda f.f^n$,所以有$0=\lambda f.\lambda x.x$,$1=\lambda f.\lambda x.fx$,$2=\lambda f.\lambda x.f(f x)$,$3=\lambda f.\lambda x.f(f(f x))$,我们定义一个后继函数(successor function)$S(n)=n+1$,即$S=\lambda n.\lambda f.\lambda x.f((n f)x)$，使用后继函数我们可以定义加法$ADD=\lambda ab.(a S)b$
\end{example}

\subsection{细胞自动机(Cellular automata)}
细胞自动机（cellular  automata）是为模拟包括自组织结构在内的复杂现象提供的一个强有力的方法，也称为元胞自动机（Cellular Automaton）。细胞自动机模型的基本思想是：自然界里许多复杂结构和过程，归根到底只是由大量基本组成单元的简单相互作用所引起。细胞自动机主要研究由小的计算机或部件，按邻域连接方式连接成较大的、并行工作的计算机或部件的理论模型。它分为固定值型、周期型、混沌型以及复杂型。\footnote{\url{https://baike.baidu.com/item/细胞自动机/2765689}}\par

细胞自动机是20世纪50年代初由计算机之父冯·诺依曼（J.von Neumann）为了模拟生命系统所具有的自复制功能而提出来的。此后，史蒂芬·沃尔夫勒姆（Stephen Wolfram）对元胞自动机理论进行了深入的研究。例如，他对一维初等元胞机全部256种规则所产生的模型进行了深入研究，并将元胞自动机分为平稳型、周期型、混沌型和复杂型 4 种类型。有关细胞自动机的系统介绍可以查看斯坦福大学斯坦福哲学百科全书网站上的“Cellular Automata”介绍\footnote{“Cellular Automata”,\url{https://plato.stanford.edu/entries/cellular-automata/}}。

\subsubsection{能够识别轮廓的细胞自动机}
下面我么举一个例子"能够识别轮廓的细胞自动机"\footnote{能够识别轮廓的细胞自动机,链接\url{https://baijiahao.baidu.com/s?id=1629331712004653022\&wfr=spider\&for=pc}}，看看细胞自动机的有趣之处，其可以用看似简单的规则，完成一些负责功能。\par

我们用一个矩形网状细胞群作为执行某些有用操作的细胞自动机示例，其中每个细胞都为黑色或白色并处于初始设置状态。
每个细胞在下一个步骤都将遵守如下规则：如果一个细胞为黑色，与之相邻的细胞为白色，那么此细胞将保持黑色，反之，细胞将变为白色。
这里，相邻细胞指的是水平或垂直相邻的任何细胞。
\par
图\ref{fig:CA-edge-detect}是细胞自动机的初始状态，我们按照上面描述的规则运行，稳定后，也就是计算结束后，我们发现这个细胞自动机运行的结果是实现了边缘检测，如图\ref{fig:CA-edge-detect-reult}所示，换句话说，此规则成功地筛选出了形状的轮廓。请注意，任何细胞都只使用了本地信息，但却成功地提取了我们可能认为是全局的东西，即轮廓。应用本地规则可以产生全局模式。。\par

\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.3\textwidth]{figure/CA-edge-detect.png}
	\caption{细胞自动机初始状态\label{fig:CA-edge-detect}}
\end{figure}

\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.3\textwidth]{figure/CA-edge-detect-result.png}
	\caption{细胞自动机停机状态\label{fig:CA-edge-detect-result}}
\end{figure}

\subsection{随机计算(Randomized Computation)}
随机计算在实践中是客观存在的，这些随机方法被成功应用到许多问题的解决中，并且得到了更简单或更高效的算法，前面提出的确定型计算模型都可以扩展到随机计算中。

\subsubsection{概率型图灵机(Probabilistic Turing machines)}
随机算法能以某种方式进行随机选择，比如随机地将变量初始化为某个范围的一个整数。在实践中，随机算法通过随机数发生器来实现。同用标准图灵机为确定型算法建模一样，我们用概率型图灵机为随机算法建模。\par

\begin{definition}{概率型图灵机(Probabilistic Turing machines，简称PTM)}{int}\cite{Arora计算复杂性}
	PTM是有两个转移函数$\delta_0,\delta_1$的图灵机，概率型图灵机M在输入x上运行时，每个步骤以1/2的概率选用转移函数$\delta_0$，以1/2的概率选用转移函数$\delta_1$。每一步的选择均独立于之前所做的所有选择。PTM只能输出1(接受)或0(拒绝)，PTM在输入x上运行结束时的输出结果是一个随机变量，记为$M(x)$，对于函数$T:N \rightarrow N$，如果概率型图灵机M在任意输入x上运行时，无论M做任何随机选择，他都在$T(|x|)$步内停机，则称M的运行时间为$T(n)$。
\end{definition}

\begin{example}
	寻找数集$\{a_1,\ldots,a_n\}$的中位数。
\end{example}
\begin{solution}
	这里给一个找k位数的一般算法$F_{IND}K_{TH}E_{LEMENT}(k,a_1,\ldots,a_n)$,输出数集中第$k$小的数，算法如下:\par
	\begin{enumerate}
		\item 随机选择$i\in [n]$,并令$x=a_i$。
		\item 扫描列表$\{a_1,\ldots,a_n\}$，统计满足$a_i\leq x$的$a_i$个数$m$。
		\item 如果$m=k$，则输出$x$。
		\item 否则，如果$m>k$，则将满足$a_i\leq x$的所有$a_i$拷贝到新列表L中，执行$F_{IND}K_{TH}E_{LEMENT}(k,L)$。
		\item 否则，如果$m<k$，则将满足$a_i> x$的所有$a_i$拷贝到新列表H中，执行$F_{IND}K_{TH}E_{LEMENT}(k-m,H)$。
	\end{enumerate}
    此算法运行时间$T(n)=O(n)$。我们通常用的确定型算法，就是先排序，然后在找中位数，其时间复杂度为$O(nlogn)$。
\end{solution}

\section{计算复杂性}

\subsection{计算复杂类}
计算复杂性是描述计算所需资源的情况，目前我们看到的基本资源有时间和空间，但不仅仅是这两种资源，还有很多其他资源比如Blum复杂度\footnote{M. Blum. "A Machine-independent theory of the complexity of recursive functions", J. ACM 14, 2, pp.322-336,1967.}，计算复杂性类就是在给定资源界限下能被计算的所有函数构成的集合。\par

\begin{definition}{DTIME类(Deterministic time class)}{int}\cite{Arora计算复杂性}
	设$T:N\rightarrow N$是一个函数，称语言$L\in DTIME(T(n))$，当且仅当存在运行时间为$c\cdot T(n)$的确定型(Deterministic)图灵机可以判定语言L，其中$c>0$是常数。
\end{definition}
DTIME中的D(Deterministic)是指确定型图灵机的意思。\par

\begin{definition}{P类(polynomial class))}{int}\cite{Arora计算复杂性}
	$P=\bigcup \limits_{c\geq 1} DTIME(n^c)$,其中c为常数。
\end{definition}

\begin{definition}{NP类(nondeterministic polynomial class))}{int}\cite{堵丁柱2002计算复杂性导论}
	语言A属于NP，当且仅当存在语言$B\in P$和多项式$p$,使得$x\in A \Leftrightarrow (\exists y,|y| \leq p(|x|)) <x,y> \in B$。
\end{definition}

非确定型计算是一个猜测加验证的计算。\par

复杂性类P(polynomial)、NP(nondeterministic polynomial)类和NPC(NP complete)之间的关系如图\ref{fig:P-NP-NPC}所示。\par

\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{figure/P-NP-NPC.png}
	\caption{P类，NP类和NPC类之间的关系\label{fig:P-NP-NPC}}
\end{figure}

除上面讲的时间复杂性，还可以研究空间复杂性，可以对图灵机执行计算过程中使用的存储单元个数进行限制，由此定义空间受限计算的概念，定义$SPACE(n)$，依次可定义PSAPCE和NPSPACE。具体概念可以参考Arora的“计算复杂性现代方法”\cite{Arora计算复杂性}。\par

关于复杂性分类，下面我们引用Oded Goldreich在其“计算复杂性”\cite{Goldreich计算复杂性}中“1.2.5 Complexity Classes”的描述。\par
Complexity classes are sets of computational problems. Typically, such classes are defined
by fixing three parameters:\par
1.A type of computational problems (see Section 1.2.2). Indeed, most classes refer to
decision problems, but classes of search problems, promise problems, and other types
of problems will also be considered.\par
2.A model of computation, which may be either uniform (see Section 1.2.3) or non-
uniform (see Section 1.2.4).\par
3.A complexity measure and a limiting function (or a set of functions), which put to-
gether limit the class of computations of the previous item; that is, we refer to the
class of computations that have complexity not exceeding the specified function (or
set of functions). For example, in §1.2.3.5, we mentioned time complexity and space
complexity, which apply to any uniform model of computation. We also mentioned
polynomial-time computations, which are computations in which the time complex-
ity (as a function) does not exceed some polynomial (i.e., a member of the set of
polynomial functions).\par
The most common complexity classes refer to decision problems, and are sometimes
defined as classes of sets rather than classes of the corresponding decision problems.
That is, one often says that a set $S\subseteq \{0, 1\}^* $is in the class C rather than saying that the
problem of deciding membership in S is in the class C. Likewise, one talks of classes
of relations rather than classes of the corresponding search problems (i.e., saying that
$R \subseteq \{0, 1\}^∗ \times \{0, 1\}^∗ $is in the class C means that the search problem of R is in the
class C).\par
\vspace{0.5cm}


\subsection{邱奇-图灵命题(Church-Turing Thesis)}
我们前面介绍了不同的计算模型，那么就存在这么个问题？不同计算模型的计算能力是否相同？或者换句话来说，不同的某一个问题属于那个计算复杂类，是否与你选择的计算模型有关？\par
邱奇-图灵命题就是来说明这个问题的。这个命题其实无法被证明，所以很多时候也称为邱奇-图灵断言。
\par
\vspace{0.5cm}
“There are various equivalent formulations of the Church-Turing thesis. A common one is that every effective computation can be carried out by a Turing machine.”\footnote{copy from \url{https://plato.stanford.edu/entries/church-turing/}}
\par
\vspace{0.5cm}

\begin{definition}{Church-Turing命题}{int}\cite{堵丁柱2002计算复杂性导论}
	如果一个函数在某个合理的计算模型上可计算，那么它在图灵机上也是可计算的。
\end{definition}

\begin{definition}{广义Church-Turing命题}{int}\cite{堵丁柱2002计算复杂性导论}
	如果一个函数在某个合理的计算模型上使用合理时间复杂性度量是多项式时间可计算的，那么它在图灵机上也是多项式时间可计算的。
\end{definition}

其实在这个描述是不严格的，比如对“合理的计算模型”就没有一个准确定义。\par

邱奇-图灵命题断言任何可被物理实现的计算装置均可被图灵机模拟，也就是说任何其他模型上的可计算问题的集合不会比图灵机上可计算问题的集合更大，所以，我么可以理解这个问题属于什么复杂类和你选择什么样的模型研究无关，他虽然不是一个可以被证明的命题，他更多是对计算或者世界本质的哲学思考\footnote{有兴趣的可以参考“The Church-Turing Thesis”,网址链接\url{https://plato.stanford.edu/entries/church-turing/}}。

\section{Uniform and Non-uniform}
在我们看一些介绍资料时通过会看到uniform model of computation 和non-uniform model of computation这两个概念。有些将uniform model翻译为“一致性模型”,将non-uniform model翻译为“非一致性模型”，uniform model是指所有的计算都可以用这个模型来表示，而non-uniform model则不行，所以将其翻译为“统一模型”个“非统一模型”也许更利于理解。\par

我们看看Oded Goldreich在其“计算复杂性”\cite{Goldreich计算复杂性}一书中的一段描述。\par
\vspace{0.5cm}
By a non-uniform model of computation we mean a model in which for each possible
input length a different computing device is considered, while there is no “uniformity”
requirement relating devices that correspond to different input lengths. Furthermore, this
collection of devices is infinite by nature, and (in the absence of a uniformity requirement)
this collection may not even have a finite description. Nevertheless, each device in the
collection has a finite description. In fact, the relationship between the size of the device
(resp., the length of its description) and the length of the input that it handles will be of
major concern.
\par
\vspace{0.5cm}

\section{Hyper computation}
Hyper computation通常我们翻译为“超计算”，是研究比图灵机有着更强计算能力的计算模型，如，图灵自己提出的“预言机”(也有翻译为“喻示机”、“神喻图灵机”)(oracle machine) 等。有很多超计算模型并没有对应的物理实现。
想进一步了解相关研究的可以阅读文献
"The many forms of hypercomputation"
\footnote{Toby Ord,	The many forms of hypercomputation,	Applied Mathematics and Computation,Volume 178, Issue 1,
	2006,Pages 143-153,url \url{http://www.amirrorclear.net/files/the-many-forms-of-hypercomputation.pdf}}

"Hypercomputation: computing more than the Turing machine"
\footnote{url \url{http://www.hypercomputation.net/download/2002a_ord.pdf}}